package datastructure;

/**
 * O(logn) for operation
 * 
 * @author yinzichen
 * 
 */
public class TreeArray {

	long[] a;
	int size;

	public TreeArray(int n) {
		a = new long[n + 1];
		size = n;
	}

	int lowbit(int n) {
		return n & (~n + 1);
	}

	public void add(int n, int v) {
		while (n <= size) {
			a[n] += v;
			n += lowbit(n);
		}
	}

	public long sum(int n) {
		long sum = 0;
		while (n > 0) {
			sum += a[n];
			n -= lowbit(n);
		}
		return sum;
	}

}
